package com.cn.wxwinnie.arithmetic;

import com.cn.wxwinnie.utils.PrintLine;

/**
 * @author 潇湘暮雨 E-mail:wxwinnie@hotmail.com
 * 
 * @version 创建时间：2014年3月11日 上午9:04:06
 * 
 */
public class ShellSort {

	public static void main(String[] args) {
		int[] aa = { 69, 45, 12, 52, 22, 65, 34, 37 };
		System.out.println();
		PrintLine.pringLine("排序前");
		System.out.println(aa);// 数组是不能直接打印的
		for (int i = 0; i < aa.length; i++) {
			System.out.print(aa[i] + " ");
		}
		System.out.println();
		PrintLine.pringLine("进入排序");
		aa = shellSort(aa);
		PrintLine.pringLine();
		PrintLine.pringLine("希尔排序后");
		for (int i = 0; i < aa.length; i++) {
			System.out.print(aa[i] + " ");
		}
	}

	public static int[] shellSort(int[] aa) {
		// 希尔排序
		int d = aa.length;
		while (true) {
			d = d / 2;
			for (int x = 0; x < d; x++) {
				for (int i = x + d; i < aa.length; i = i + d) {
					int temp = aa[i];
					int j;
					for (j = i - d; j >= 0 && aa[j] > temp; j = j - d) {
						aa[j + d] = aa[j];
					}
					aa[j + d] = temp;
				}
			}
			if (d == 1) {
				break;
			}
		}

		return aa;
	}
}